class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int len = nums.size();
    int left = 0;
    int right = len - 1;
    int target = len - k;

    while (true) {
      int index = partition(nums, left, right);
      if (index == target)
        return nums[index];
      else if (index < target)
        left = index + 1;
      else
        right = index - 1;
    }
    return -1;
  }
  int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[left];
    int j = left;
    for (int i = left + 1; i <= right; ++i) {
      if (nums[i] < pivot) {
        j++;
        swap(nums[i], nums[j]);
      }
    }
    swap(nums[j], nums[left]);
    return j;
  }
};
